#include "yufa.h"
using namespace std;

int wenfaCounts = 0;
int Row = 0;
int Line = 0;
void first_create();
void follow_create();
void table_create();
set<string> Get_FIRST(string r);
bool IsNumber(char x);
void FenXi();

void first_create()
{ //构建FIRS集合
    int changenums = 1;
    //对于终结符来说，其first集就是其本身
    for (string x : Zhongjie)
    {
        set<string> temp;
        /*if(x == "GROUP_BY expression"){
            x ="GROUP_BY";
        }*/
        temp.insert(x);
        FIRST[x] = temp;
    }
    while (changenums)
    {
        changenums = 0;
        for (string x : false_Zhongjie)
        {

            set<string> Right;
            Right = set_get(x);
            set<string> first = FIRST[x];
            for (string r : Right)
            {
                if ((first.empty() || (!set_in("$", first)) && !(!r.compare("$") == 0)))
                {
                    first.insert(r);
                    changenums = 1;
                }
                else
                {
                    istringstream str(r);
                    string ou;
                    // bool R = true;
                    int RS = 1;
                    while (str.good())
                    {
                        getline(str, ou, ' ');
                        if (ou.empty())
                        {
                            cout << "ou empty error" << endl;
                            break;
                        }
                        string out = ou;
                        if (In_Feizhong(out) && FIRST[out].empty())
                        {
                            changenums = 1;
                            break;
                        }
                        else if (In_Zhongjie(out))
                        {
                            first.insert(out);
                            if ((!set_in(out, first) || first.empty()))
                            {
                                changenums = 1;
                            }
                            break;
                        }
                        else if (In_Feizhong(out))
                        {
                            if (!set_commpare(first, FIRST[out], false))
                            {

                                changenums = 1;
                                if (set_in("$", FIRST[out]) && !str.good())
                                { 
                                    first = set_connent(first, FIRST[out], 0);
                                }
                                else if (set_in("$", FIRST[out]))
                                {
                                    first = set_connent(first, FIRST[out], 1);
                                    continue;
                                }
                                else if (!set_in("$", FIRST[out]))
                                {
                                    first = set_connent(first, FIRST[out], 0);
                                    break;
                                }
                            }
                            else
                            {

                                changenums = 0;
                                break;
                            }
                        }
                        else
                        {

                            changenums = 0;
                        }
                    }
                }
            }

            FIRST[x] = first;
        }
    }
}

void follow_create()
{
    set<string> s;
    s.insert("#");
    FOLLOW["S"] = s;
    // FOLLOW["iteration_stmt"] = s;

    int changnums = 1;
    int test = 25;

    while (changnums && test)
    {
        test--;
        changnums = 0;
        for (string x : false_Zhongjie)
        { //遍历更新非终结符集合
            set<string> Right;
            Right = set_get(x);
            set<string> follow = FOLLOW[x];
            for (string r : Right)
            { //右侧产生式
                stack<string> temp;
                queue<string> temp2;
                istringstream str(r);
                string ou;

                while (str.good())
                {
                    getline(str, ou, ' ');
                    temp.push(ou);
                    temp2.push(ou);
                }
                int t = temp2.size();
                string* right = new string[t];
                //string right[t];
                int counts = 0;
                for (int i = 0; i < t; i++)
                {
                    if (temp2.front().compare("\n") != 0 && temp2.front().compare(" ") != 0 &&
                        temp2.front().length() != 0 && temp2.front().compare("") > 0 && temp2.front().compare("\r") != 0)
                    {
                        right[counts] = temp2.front();
                        counts++;
                    }
                    temp2.pop();
                }
                t = counts;
                // cout <<" counts"<<t<<" ";
                for (int i = 0; i < t; i++)
                { //遍历更新
                    if (i == t - 1 && In_Feizhong(right[i]) && (!set_commpare(FOLLOW[right[i]], FOLLOW[x], false) || FOLLOW[right[i]].empty()))
                    {
                        //非终结符
                        // cout<<"F"<<x<<" update "<<right[i]<<endl;
                        changnums = 1;
                        FOLLOW[right[i]] = set_connent(FOLLOW[right[i]], FOLLOW[x], 0);
                    }
                    else if (In_Feizhong(right[i]) && i < t - 1)
                    { 
                        if (In_Feizhong(right[i + 1]))
                        {
       
                            for (int j = i + 1; j < t; j++)
                            {
                            
                                if (In_Feizhong(right[j]) && (!set_commpare(FOLLOW[right[i]], FIRST[x], true) || FOLLOW[right[i]].empty()))
                                {

                                    changnums = 1;
                                    FOLLOW[right[i]] = set_connent(FOLLOW[right[i]], FIRST[x], 1);
                                }
                                if (!set_in("$", FIRST[right[j]]))
                                {
                                 
                                    break;
                                }
                            }
                        }
                        else
                        {
                            if (!set_in(right[i + 1], FOLLOW[right[i]]) || FOLLOW[right[i]].empty())
                            {
                              

                                changnums = 1;
                                FOLLOW[right[i]] = set_connent(FOLLOW[right[i]], FIRST[right[i + 1]], 0);
                            }
                        }
                    }
                    else
                    {
                        continue;
                    }
                }
                delete[] right;
                right = NULL;
            }
        }
    }
    return;
}

void table_create()
{
    queue<string> temp;
    int x = 0;
    for (string tx : Zhongjie)
    {
        temp.push(tx);
        x++;
    }
    string* row0 = new string[x+1];
    //string row0[x + 1];
    row0[0] = "";

    for (int i = 1; i < x + 1; i++)
    {
        row0[i] = temp.front();
        temp.pop();
    }

    vector<string> r0(row0, row0 + x + 1);
    Row = x + 1;
    table.push_back(r0);
    int y = 1;
    for (string FZ : false_Zhongjie)
    {
        vector<string> tempVector;
        set<string> Right = set_get(FZ);
        tempVector.push_back(FZ);

        for (int j = 1; j < Row; j++)
        {
            bool judge = true;
            int writecounts = 0;
            string tempa = r0.at(j);
            // cout <<tempa+":" ;
            for (string r : Right)
            {
                if (FIRST[r].empty())
                {
                    FIRST[r] = Get_FIRST(r);
                }
                if (set_in(tempa, FIRST[r]) || (set_in("$", FIRST[r]) && set_in(tempa, FOLLOW[FZ]) && r.compare("$") != 0))
                {
                    judge = false;
                    writecounts++;
                    /*if(r == "GROUP BY expressions"){
                         r = "GROUP_BY expressions";
                     }*/
                    tempVector.push_back(FZ + "->" + r);
                    break;
                }
            }

            if (writecounts == 0)
            {
                tempVector.push_back("");
            }
        }
        table.push_back(tempVector);
        y++;
    }
    Line = y;
    delete[] row0;
    row0 = NULL;
    return;
}

set<string> Get_FIRST(string r)
{
    set<string> result;
    queue<string> temp2;
    istringstream str(r);
    string ou;
    while (str.good())
    {
        getline(str, ou, ' ');
        temp2.push(ou);
    }
    int t = temp2.size();
    string* right = new string[t];
   // string right[t];
    int counts = 0;
    for (int i = 0; i < t; i++)
    {
        if (temp2.front().length() > 0)
        {
            right[counts] = temp2.front();
            counts++;
        }
        temp2.pop();
    }
    t = counts;
    for (int i = 0; i < t; i++)
    {
        if (i == t - 1)
        {
            result = set_connent(result, FIRST[right[i]], 0);
        }
        else if (In_Zhongjie(right[i]))
        {
            result = set_connent(result, FIRST[right[i]], 0);
            break;
        }
        else if (In_Feizhong(right[i]))
        {
            result = set_connent(result, FIRST[right[i]], 1);
            if (!set_in("$", FIRST[right[i]]))
            {
                break;
            }
        }
    }
    delete[] right;
    right = NULL;
    return result;
}

bool IsNumber(char x)
{
    return (x >= '0' && x <= '9');
}
ofstream GUIYUE;
void FenXi()
{

    string stacktop;
    string tokentop;
    stack<string> FuHao;
    queue<string> TempToken = Token;
    string ShiZi;
    FuHao.push("#");
    FuHao.push("root");
    GUIYUE.open("guiyue.txt",ios::out);
    // cout<<FuHao.size()<<endl;
    int num1 = 1;
    /*for(int i = 0;i<TempToken.size();i++){
        cout<<TempToken.front()<<endl;
        TempToken.push(TempToken.front());
        TempToken.pop();
    }*/
    while (!Token.empty())
    {
        stacktop = FuHao.top();
        tokentop = TempToken.front();
      // cout<<"stacktop为"<<stacktop<<endl;
        //cout<<"tokentop为"<<tokentop<<endl;
        ShiZi = get_table(stacktop, tokentop);
       cout<<"规约式为"<<ShiZi<<endl;
        if (ShiZi.compare("#") == 0)
        {
            cout << "error" << endl;
        }
    
        if ((stacktop.compare(tokentop) == 0)&&(tokentop.compare("#")!=0))
        {
            cout << num1 << "   "
                 << "/"
                 << "   " << stacktop << "#" << tokentop << "     "
                 << "move" << endl;
            GUIYUE<< num1 << "   "
                 << "/"
                 << "   " << stacktop << "#" << tokentop << "     "
                 << "move" << endl;
            
            FuHao.pop();
            TempToken.pop();
            /* for(int i = 0;i<TempToken.size();i++){
              cout<<"pop之后的首元素"<<TempToken.front()<<endl;
              TempToken.push(TempToken.front());
              TempToken.pop();
              }
              cout<<"首元素为"<<FuHao.top()<<endl;
                cout<<"栈顶元素为"<<TempToken.size()<<endl;*/
            /*if(TempToken.size() == 0&&stacktop.empty()){
                  cout << num1+1 << "   " <<"1"<< "    " << "##" << "    "
                   << "accept" << endl;*/
            // }*/
        }

        else
        {
            int num2 = 0;
            while (stacktop.compare(wenfa[num2][0]) != 0)
            {
                num2++;
                //cout<<num2<<endl;
                if (num2 > 180)
                {
                    num2 = 0;
                    break;
                }
            }
            /*if(tokentop.compare("GROUPBY")==0&&stacktop.empty()){
                 cout << num1 << "   " << num2+1 << "    " << stacktop << "#" << tokentop << "    "
                     << "accept" << endl;
            }
            if(tokentop.compare("GROUPBY")==0&&stacktop.compare(""))*/
            if (stacktop.compare("#") == 0 /*&&/*tokentop.empty()*/)
            {
                if(tokentop.compare("#"))
                {
                    cout << num1 << "   " << "/" << "    " << stacktop << "#" << tokentop << "    "
                     << "accept" << endl;
                GUIYUE<< num1 << "   " << "/" << "    " << stacktop << "#" << tokentop << "    "
                     << "accept" << endl;
                }
                else{
                    cout << num1 << "   " << "/" << "    " << stacktop << "#" << "    "
                     << "accept" << endl;
                    GUIYUE<< num1 << "   " << "/" << "    " << stacktop << "#" << "    "
                     << "accept" << endl;
                }
                // cout << "shizi = " << ShiZi << endl;
            }
            else
            {
                if (TempToken.size() == 0)
                {
                    cout << num1 << "   " << num2 + 1 << "    " << stacktop << ""
                         << "#"
                         << "    "
                         << "reduction" << endl;
                    GUIYUE<< num1 << "   " << num2 + 1 << "    " << stacktop << ""
                         << "#"
                         << "    "
                         << "reduction" << endl;
                    // cout << "shizi = " << ShiZi << endl;
                }
                else
                {    
                    if(tokentop.compare("#"))
                    {cout << num1 << "   " << num2 + 1 << "    " << stacktop << "#"
                         << tokentop
                         << "    "
                         << "reduction" << endl;
                    GUIYUE<< num1 << "   " << num2 + 1 << "    " << stacktop << "#"
                         << tokentop
                         << "    "
                         << "reduction" << endl;
                    }
                    else{
                    cout << num1 << "   " << num2 + 1 << "    " << stacktop << "#"
                         << "    "
                         << "reduction" << endl;
                    GUIYUE<< num1 << "   " << num2 + 1 << "    " << stacktop << "#"
                         << "    "
                         << "reduction" << endl;
                }
                }
                if (TempToken.size()==0)
            {
                TempToken.push("#");
            }
            }
            string tempright;

            for (int i = 0; i < ShiZi.length(); i++)
            {
                if (ShiZi[i] == '-' && ShiZi[i + 1] == '>')
                {

                    tempright = ShiZi.substr(i + 2, ShiZi.length() - i - 2);
                }
            }

            stack<string> tempstack;
            istringstream str(tempright);
            string out;
            while (str.good())
            {
                getline(str, out, ' ');
                if (out.length() > 0)
                    tempstack.push(out);
            }

            FuHao.pop();
            while (!tempstack.empty())
            {
                if (!(tempstack.top().compare("$") == 0))
                    FuHao.push(tempstack.top());

                tempstack.pop();
            }
            
        }
        num1++;
    }

    return;
}

int main()
{
    Deal_Wenfa();
    // for(int i = 0;i<200;i++)
    // cout<<wenfa[i][0] << "  "<<wenfa[i][1]<<endl;
    First.open("first.txt");
    Follow.open("follow.txt");
    first_create();
    first_write();
    follow_create();
    write_fellow();
    table_create();
    write_table();
    read_token();
    FenXi();

    return 0;
}